/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package br.ufrgs.inf.inf05005.automatos;

import br.ufrgs.inf.inf05005.utils.Utils;
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * File pattern
 * 
 * Atenção: o nome do autômato não é AUTÔMATO, pode ser qualquer palavra
 * 
 * AUTÔMATO=({q0,q1,q2,q3},{a,b},q0,{q1,q3}) 
 * Prog 
 * (q0,a)=q1 
 * (q0,b)=q2 
 * (q1,b)=q2
 * (q2,a)=q3 
 * (q2,a)=q2 
 * (q3,a)=q3 
 * (q3,b)=q2
 */
public class Automato {
    // variaveis que definem o automato

    protected ArrayList<String> estados = null;
    protected ArrayList<String> alfabeto = null;
    protected String estadoInicial = null;
    protected ArrayList<String> estadosFinais = null;
    protected static String[][] tabelaDeTransicao = null;
    // variaveis de trabalho
    protected String estadoAtual;
    protected String palavraParaReconhecer;

    /**
     * Construtor: carrega o arquivo e prepara a função de transição
     * 
     * @param o arquivo escolhido pelo usuário
     */
    public Automato(File file) throws Exception {
        FileInputStream fstream = null;
        fstream = new FileInputStream(file);

        // Get the object of DataInputStream
        DataInputStream in = new DataInputStream(fstream);
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        // Read File Line By Line
        try {
            /*
             * A primeira linha define o autômato
             */
            // regex que separa a definição do automato em grupos principais
            Pattern p = Pattern.compile(Utils.PATTERN_AUTOMATON_DEF);
            String line = br.readLine();
            Matcher matcher = p.matcher(line);
            if (matcher.find() && matcher.groupCount() == 4) {
                Boolean valid = true;
                // testa se cada grupo principal está num padrão 
                // (dado por regex individuais) e prepara os ArrayLists se ok
                if (testGroup(matcher.group(1), Utils.PATTERN_STATES)) {
                    estados = convertGroup(matcher.group(1));
                } else {
                    valid = false;
                }
                if (testGroup(matcher.group(2), Utils.PATTERN_ALFABET)) {
                    alfabeto = convertGroup(matcher.group(2));
                } else {
                    valid = false;
                }
                if (testGroup(matcher.group(3), Utils.PATTERN_STATE)) {
                    estadoInicial = convertGroup(matcher.group(3)).get(0);
                } else {
                    valid = false;
                }
                if (testGroup(matcher.group(4), Utils.PATTERN_STATES)) {
                    estadosFinais = convertGroup(matcher.group(4));
                } else {
                    valid = false;
                }
                // validate automaton definition
                if (!valid) {
                    throw new Exception("A definição do AFND é inválida (um dos conjuntos está incorreto)");
                }
                System.out.println("States: " + estados.toString()
                        + "\nAlfabet: " + alfabeto.toString()
                        + "\nInitial state: " + estadoInicial.toString()
                        + "\nFinal states: " + estadosFinais.toString());


            } else {
                throw new Exception("A definição do AFND é inválida..");
            }

            /*
             * A segunda linha vai fora, só contém 'Prog'
             */
            br.readLine();
            /*
             * A tabela de transição tem um número indefinido de linhas,
             * pois cada linha é um estado. Mas o número de colunas é dado
             * pelo número de símbolos do alfabeto.
             * Contamos uma coluna e uma linha extra para os rótulos.
             */
            tabelaDeTransicao = new String[estados.size() + 1][alfabeto.size() + 1];
            tabelaDeTransicao[0][0] = String.valueOf(estados.size() + 1) + "," + String.valueOf(alfabeto.size() + 1);
            // coloca cada símbolo do alfabeto numa coluna, na linha 0 - de rótulos. --|a|b|
            for (int i = 0; i < alfabeto.size(); i++) {
                tabelaDeTransicao[0][i + 1] = alfabeto.get(i);
            }
            // coloca cada estado numa linha, na coluna 0 - de rótulos.
            // --
            // q0
            // q1
            for (int i = 0; i < estados.size(); i++) {
                tabelaDeTransicao[i + 1][0] = estados.get(i);
            }

            /**
             * Leio cada linha da tabela, testando quanto à regex,
             * e insiro as informações na tabela de acordo com o 
             * estado atual e o símbolo lido.
             */
            p = Pattern.compile("\\((.\\d)+,(.)\\)=(.\\d)");
            while ((line = br.readLine()) != null) {
                matcher = p.matcher(line);
                if (!matcher.find()) {
                    throw new Exception("Transição mal interpretada.");
                }
                // matcher.group(1); // estado atual
                // matcher.group(2); // símbolo lido 
                // matcher.group(3); // estado futuro
                // acha linha e coluna
                int li = findLine(matcher.group(1), tabelaDeTransicao);
                int co = findColumn(matcher.group(2), tabelaDeTransicao);
                if (tabelaDeTransicao[li][co] == null) {
                    tabelaDeTransicao[li][co] = matcher.group(3);
                } else {
                    tabelaDeTransicao[li][co] += Utils.PATTERN_SEPARATOR + matcher.group(3);
                    // colocar em ordem (decrescente) para não avacalhar as comparações
                    ArrayList<String> paraOrdenarAL = new ArrayList<String>(Arrays.asList(tabelaDeTransicao[li][co].split(Utils.PATTERN_SEPARATOR)));
                    Comparator comparator = Collections.reverseOrder();
                    Collections.sort(paraOrdenarAL, comparator);
                    String[] jhjhj = new String[paraOrdenarAL.size()];
                    jhjhj = paraOrdenarAL.toArray(jhjhj);
                    tabelaDeTransicao[li][co] = colapseArray(jhjhj, Utils.PATTERN_SEPARATOR);
                }
            }
            Utils.printMatrix(tabelaDeTransicao);
            in.close();
        } catch (IOException e1) {
            throw new Exception("Wrong header");
        }
    }

    /**
     * Tranforma o automato possivelemnte não-determinista
     * num automato determinista
     */
    public void determiniza() {
        // os estados finais vão, provavelmente, mudar
        ArrayList<String> estadosFinaisTemp = new ArrayList<String>();
        // aqui ficarão os estados por inserir e os já inseridos
        ArrayList<String> estadosPorInserir = new ArrayList<String>();
        ArrayList<String> estadosInseridos = new ArrayList<String>();
        // pega o numero de linhas e colunas da tabela não-deterministica
        int co = getCO(tabelaDeTransicao);
        // cria uma nova tabela, só com a linha de símbolos
        String[][] matrix = new String[1][co];
        // copia a linha de símbolos
        System.arraycopy(tabelaDeTransicao[0], 0, matrix[0], 0, co);
        // faz update das informações de linhas e colunas em 0,0
        matrix[0][0] = "1," + co;
        // insere o primeiro estado
        estadosPorInserir.add(estadoInicial);
        // e, eqnuanto houver estados por inserir...
        while (!estadosPorInserir.isEmpty()) {
//            System.out.println("Ainda há " + estadosPorInserir + " por inserir.");
            int li = getLI(matrix);
            // pegamos um dos estados
            String estado = estadosPorInserir.get(0);
            // removemos da lista por inserir
            estadosPorInserir.remove(0);
            // verificamos se já inserimos antes
            if (!estadosInseridos.contains(estado)) {
//                System.out.println(" Estado " + estado + " não está nos já inseridos " + estadosInseridos.toString() + ", preparar para inserir.");
                // aumenta uma linha na tabela
                String[][] temp = new String[li + 1][co];
                // copia os antigos dados pra dentro
                for (int i = 0; i < li; i++) {
                    System.arraycopy(matrix[i], 0, temp[i], 0, co);
                }
                // coloca o novo estado dentro
                temp[li][0] = estado;
                // como inserimos um estado, fazemos update em 0,0
                temp[0][0] = String.valueOf(li + 1) + Utils.PATTERN_SEPARATOR + String.valueOf(co);
                // coloca o estado nos estados inseridos
                estadosInseridos.add(estado);
                // como já vamos inserir, remove
                estadosPorInserir.remove(estado);
                // é um novo estado
                temp[li][0] = estado;
                // acha a linha (se houver) com o estado na tabela antiga.
                int liEstTabTrans = findLine(estado, tabelaDeTransicao);
                if (liEstTabTrans > 0) {
//                    System.out.println("  Estado " + estado + " estava na tabela anterior, na linha " + liEstTabTrans);
//                    System.out.print("  Inserindo ");
                    for (int i = 1; i < co; i++) {
                        String estadoTemp = tabelaDeTransicao[liEstTabTrans][i];
                        temp[li][i] = estadoTemp;
                        if (estadoTemp != null) {
                            System.out.print(estadoTemp + ", ");
                            // coloca os estados encontrados na lista de estados por inserir
                            estadosPorInserir.add(estadoTemp);
                            // verifica se é um estado final
                            if (estadosFinais.contains(estadoTemp) && !estadosFinaisTemp.contains(estadoTemp)) {
                                estadosFinaisTemp.add(estadoTemp);
                            }
                        }
                    }
//                    System.out.println("");
                } else {
//                    System.out.println("  Estado " + estado + " não estava na tabela anterior. Preparar para criar seus estados futuros.");
                    // gravar os estados futuros do novo estado
                    // para isso, quebraremos o estado em seus subestados
                    String[] subEstados = estado.split(Utils.PATTERN_SEPARATOR);
                    // construiremos uma "matriz" de cada estado futuro, de cada sub-estado
                    ArrayList<String[]> estadosFuturosDosSubEstados = new ArrayList<String[]>();
                    // então, para cada subestado
                    for (int s = 0; s < subEstados.length; s++) {
//                        System.out.print("   O subestado " + subEstados[s]);
                        // acho sua linha na tabela de transição original
                        int liSubEstTabTrans = findLine(subEstados[s], tabelaDeTransicao);
                        // se achei
                        if (liSubEstTabTrans > 0) {
//                            System.out.println(" está na linha " + liSubEstTabTrans + " da tabela anterior.");
                            // procuro suas transições na tabela de transição original
                            String[] estFutSubEstadoComponente = new String[co];
                            for (int i = 0; i < co; i++) {
                                //copio um array com suas transições
                                estFutSubEstadoComponente[i] = tabelaDeTransicao[liSubEstTabTrans][i];
                            }
//                            System.out.print("    Armazenando estados futuros ");
                            Utils.printArray(estFutSubEstadoComponente);
                            // adiciono esta linha na "matriz"
                            estadosFuturosDosSubEstados.add(estFutSubEstadoComponente);
                        } else {
//                            System.out.println(" não está na tabela anterior.");
                            // se não achei...
                            System.out.println("    What now?");
                        }
                        // verifica se é um estado final
                        if (estadosFinais.contains(subEstados[s]) && !estadosFinaisTemp.contains(estado)) {
                            estadosFinaisTemp.add(estado);
                        }
                    }
//                    System.out.println("  De 0 a " + estadosFuturosDosSubEstados.size());
                    ArrayList<String> estadao = null;
                    String estadaoS = null;
                    // com a matriz pronta, devemos criar os estados futuros compostos
                    for (int i = 0; i < estadosFuturosDosSubEstados.size(); i++) {
                        // componho um estado com o valor (não-nulo) de cada coluna
//                        System.out.println("   De 0 a " + co);
                        for (int j = 1; j < co; j++) {
                            String[] estadosFuturosDoSubEstado = estadosFuturosDosSubEstados.get(i);
                            if (estadosFuturosDoSubEstado[j] != null) {
                                // verifica o tipo de composição a fazer
                                if (estadao == null) {
                                    estadao = new ArrayList<String>();
                                    // quebra o estado a inserir
                                    String[] subEstadosEstadoFuturo = estadosFuturosDoSubEstado[j].split(Utils.PATTERN_SEPARATOR);
                                    estadao.addAll(Arrays.asList(subEstadosEstadoFuturo));
                                } else {
                                    // ao compor, verifica se esse estado futuro já não faz parte do estadao
                                    String[] subEstadosEstadoFuturo = estadosFuturosDoSubEstado[j].split(Utils.PATTERN_SEPARATOR);
                                    for (int k = 0; k < subEstadosEstadoFuturo.length; k++) {
                                        if (!estadao.contains(subEstadosEstadoFuturo[k])) {
                                            estadao.add(subEstadosEstadoFuturo[k]);
                                        }
                                    }
                                }
//                                System.out.println("Estadao " + estadao.toString());
                                // coloca o estadao em ordem (decrescente) para não avacalhar as comparações
                                Comparator comparator = Collections.reverseOrder();
                                Collections.sort(estadao, comparator);
                                // temp recebe o novo estado de destino
                                String[] estadaoArray = new String[estadao.size()];
                                estadaoArray = estadao.toArray(estadaoArray);
                                estadaoS = colapseArray(estadaoArray, Utils.PATTERN_SEPARATOR);
                                temp[li][j] = estadaoS;
                                estadao = null;
                            }

                        }
                        estadosPorInserir.add(estadaoS);
                        estadaoS = null;
                    }
                }
                matrix = temp;
            } else {
//                System.out.println("Estado " + estado + " está nos já inseridos " + estadosInseridos.toString() + ", removendo-o");
                // como já foi inserido, remove
                estadosPorInserir.remove(estado);
            }
        }
        tabelaDeTransicao = matrix;
        // os estados oficiais do autômato são, agora, todos os inseridos
        estados = estadosInseridos;
        // os estados finais do autômato são, agora, os que guardamos
        estadosFinais = estadosFinaisTemp;
    }

    /**
     * Colapsa um array de strings numa string.
     * @param array
     * @param separator
     * @return a string
     */
    private String colapseArray(String[] array, String separator) {
        String colapsedArray = "";
        for (int i = 0; i < array.length; i++) {
            if (i != 0 && i != array.length) {
                colapsedArray += separator;
            }
            colapsedArray += array[i];
        }
        return colapsedArray;
    }

    /**
     * Testa a string fornecida (um grupo reconhecido pela regex principal)
     * segundo a regex fornecida junto. Caso o grupo satisfaça a regex, retorna
     * true
     * 
     * @param group
     *            string a analisar
     * @param regex
     *            para testar a string
     * @return true se a regex foi satisfeita
     */
    private boolean testGroup(String group, String regex) {
        Pattern p = Pattern.compile(regex);
        if (p.matcher(group).find()) {
            return true;
        }
        return false;
    }

    /**
     * Dado um grupo de estados, separado por vírgula, retorna o
     * ArrayList<String> contendo os estados
     * 
     * @param group
     *            uma string com os estados separados por vírgulas
     * @return ArrayList<String> com os estados
     */
    private ArrayList<String> convertGroup(String group) {
        ArrayList<String> temp = null;
        String[] statesArray = group.split(",");
        for (String state : statesArray) {
            if (temp == null) {
                temp = new ArrayList<String>();
            }
            temp.add(state);
        }
        return temp;
    }

    /**
     * Acha o número da coluna onde está o símbolo
     * @param simbolo
     * @param matrix
     * @return 
     */
    private int findColumn(String simbolo, String[][] matrix) {
        int co = getCO(matrix);
        // encontra a coluna
        for (int i = 0; i < co; i++) {
            if (simbolo.equals(matrix[0][i + 1])) {
                return i + 1;
            }
        }
        return -1;
    }

    /**
     * Dado um estado, acha sua linha
     * @param state
     * @param matrix
     * @return -1 se não acha
     */
    private int findLine(String state, String[][] matrix) {
        if (state == null || matrix == null) {
            return -1;
        }
        int li = getLI(matrix);
        // encontra a coluna
        for (int i = 1; i < li; i++) {
            if (state.equals(matrix[i][0])) {
                return i;
            }
        }
        return -1;
    }

    /**
     * Acha o número de linhas da matriz
     * (A partir da informação codificada em 0,0)
     * @param matrix
     * @return int com o número de linhas da matriz
     */
    private int getLI(String[][] matrix) {
        if (matrix == null) {
            return 0;
        }
        String[] lico = matrix[0][0].split(",");
        return Integer.parseInt(lico[0]);
    }

    /**
     * Acha o número de colunas da matriz.
     * (A partir da informação codificada em 0,0)
     * @param matrix
     * @return 
     */
    private int getCO(String[][] matrix) {
        if (matrix == null) {
            return 0;
        }
        String[] lico = matrix[0][0].split(",");
        return Integer.parseInt(lico[1]);
    }

    /**
     * GETTERS AND SETTERS
     */
    /**
     * Retorna um ArrayList<String> contento os simbolos do alfabeto
     * @return 
     */
    public ArrayList<String> getAlfabeto() {
        return alfabeto;
    }

    /**
     * Retorna um ArrayList<String> contento o estado inicial
     * @return 
     */
    public String getEstadoInicial() {
        return estadoInicial;
    }

    /**
     * Retorna um ArrayList<String> contento o estados do autômato
     * @return 
     */
    public ArrayList<String> getEstados() {
        return estados;
    }

    /**
     * Retorna um ArrayList<String> contento oestados finais do automato
     * @return 
     */
    public ArrayList<String> getEstadosFinais() {
        return estadosFinais;
    }

    /**
     * Retorna a tabela de transição do autômato.
     * Atenção: por definição, este autômato pode ser não determinístico.
     * Nesse caso, os campos da tabela (com os próximos estados)
     * estarão na forma q0,q1,...,qn - separados por vírgulas.
     * Atenção: os campos serão nulos se a transição for indefinida, testar.
     * @return String[][] da tabela de transição, na forma 
     * "linhas,colunas" | simbolo1 | simbolo2 | ... | simboloN
     * estadoAtual1     | proxEst  | null     | ... | null
     *  ...                      ...                    ...
     * estadoAtual2     | null     | proxEst  | ... | proxEst
     */
    public String[][] getTabelaDeTransicao() {
        return tabelaDeTransicao;
    }

    /**
     * Retorna o estado em que o automato está
     * @return 
     */
    public String getEstadoAtual() {
        return estadoAtual;
    }

    /**
     * Retorna a palavra que o automato tenta(ou) reconhecer
     * @return 
     */
    public String getPalavraParaReconhecer() {
        return palavraParaReconhecer;
    }

    /**
     * Seta a palavra que o automato deve reconhecer
     * @param palavraParaReconhecer 
     */
    public void setPalavraParaReconhecer(String palavraParaReconhecer) {
        this.palavraParaReconhecer = palavraParaReconhecer;
    }
}